package com.xzz.bfs;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: hhz
 * @create: 2022-01-21 09:19
 * 1345. 跳跃游戏 IV
 **/
public class MinJumps {
    public static void main(String[] args) {
//        System.out.println(minJumps(new int[]{100,-23,-23,404,100,23,23,23,3,404}));
//        System.out.println(minJumps(new int[]{7}));
        System.out.println(minJumps(new int[]{0,4,3,9}));
    }
    public static int minJumps(int[] arr) {
        if(arr.length==1){
            return 0;
        }
        HashMap<Integer, LinkedList<Integer>> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            int key = arr[i];
            if(map.containsKey(key)){
                map.get(key).add(i);
            }else {
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                map.putIfAbsent(key,list);
            }
        }
        int res = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        //记录节点是否访问过
        boolean[] visited = new boolean[arr.length];
        visited[0] = true;
        //记录节点是否使用了[等值跳]
        boolean[] op3 = new boolean[arr.length];
        while (!queue.isEmpty()){
            int size = queue.size();
            res ++;
            for (int i = 0; i < size; i++) {
                Integer poll = queue.poll();
                //i+1
                if(poll+1==arr.length-1){
                    return res;
                }
                if(!visited[poll+1]){
                    queue.offer(poll+1);
                    visited[poll+1] = true;
                }
                //i-1
                if(poll-1>0 && !visited[poll-1]){
                    queue.offer(poll-1);
                    visited[poll-1] = true;
                }
                //arr[i] == arr[j] 且 i != j
                if(!op3[poll]){
                    op3[poll]=true;
                    LinkedList<Integer> list = map.get(arr[poll]);
                    for (Integer next : list) {
                        op3[next] = true;
                        if(!visited[next]){
                            if(next==arr.length-1){
                                return res;
                            }
                            visited[next] = true;
                            queue.offer(next);
                        }

                    }
                }

            }
        }
        return -1;
    }
}
